//题号：五、14
#include <iostream>
#include <climits>
#include <vector>
using namespace std;
int N;
int **graph;
int A2B_straight(int A, int B) {
    return graph[A - 1][B - 1];
}

void Dijkstra(int A, int distance[], int path[], int path_count[]) {
    bool S[N];

    // 初始化 distance、path 和 path_count
    for (int i=1;i<=N;i++) {
        distance[i-1]=A2B_straight(A,i);
        S[i-1] = false;
        if (i!=A&&distance[i-1] < INT_MAX) {
            path[i-1]=A;
            path_count[i-1]=1; // 初始路径经过 1 个顶点
        } else {
            path[i-1]=-1;
            path_count[i-1] = INT_MAX;
        }
    }

    S[A-1] = true;
    distance[A-1] = 0;
    path_count[A-1] = 0; // 源点到自身的路径经过 0 个顶点

    for (int i=0;i<N-1;i++) {
        int min=INT_MAX;
        int stop=A;
        for (int j=1;j<=N;j++) {
            if (!S[j-1]&&distance[j-1]<min) {
                min=distance[j-1];
                stop=j;
            }
        }
        S[stop-1] = true;

        for (int k=1;k<=N;k++) {
            int length2=A2B_straight(stop,k);
            if (!S[k-1]&&length2<INT_MAX&&distance[stop-1]+length2<distance[k-1]){
                distance[k-1] = distance[stop-1] + length2;
                path[k-1] = stop;
                path_count[k-1] = path_count[stop-1]+1; // 更新路径经过的顶点数
            } else if (!S[k-1] && length2<INT_MAX && distance[stop-1] + length2==distance[k-1]) {
                // 如果距离相同，选择经过顶点数最少的路径
                if (path_count[stop-1]+1<path_count[k-1]){
                    path[k-1]=stop;
                    path_count[k-1]=path_count[stop-1]+1;
                }
            }
        }
    }
}

